A Vehicular Ad Hoc Network (VANET) consists of a group of vehicles that communicate with each other through on-board wireless communication modules. One of the most important applications for VANET is the broadcast of real-time safety advisories and/or warning messages from vehicles that sense the situation of the vehicles nearby or behind. This class of applications, called Safety-Critical Application (SCA), requires timely and reliable message dissemination.
VANETs, like other wireless data networks such as WiFi (IEEE 802.11) or cellular networks (e.g. UMTS), must employ a MAC (Medium Access Control) protocol to dynamically allocate the radio channels available in the spectrum to the nodes in the network for data transmission, where the nodes may join or leave the network at any time. The section in the MAC protocol that implements this function is called the channel access scheme. In addition, the MAC protocol is also responsible for assembling incoming data frames received from the PHY (Physical) layer into packets and forwarding the packets to the upper layer, as well as for disassembling outgoing packets into bits that can be further processed by the PHY layer and transmitted. The design of the MAC protocol depends on factors including the available spectrum, the speed of the nodes, the bandwidth/delay requirements of the applications, etc.
The design of a channel access scheme for VANET poses new challenges that are not seen in the MAC design for WiFi or cellular networks. In comparison to WiFi, the nodes (i.e. vehicles) in a VANET are moving at a very high speed, much higher than the nodes in a WiFi network (which typically are stationary devices or nomadic user devices). The implication is that the VANET MAC must be able to assign channels to a node at a very short response time, much shorter than is allowed in the WiFi network, in order to ensure timely transmission of the data from the node (e.g., before the vehicle moves out of the range of a VANET cluster).
In comparison to the UMTS cellular data network, the VANET does not have infrastructure support (such as base station and base station controller which are all stationary elements) and thus the medium access control must rely on a distributed scheme among the mobile nodes (vehicles) in the network. There is no single fixed entity in a VANET that will collect ancillary information and perform medium access control.
In summary, the challenges related to the MAC design of VANET for message broadcasting include:
Mobility: the MAC protocol should support vehicles that leave and join the VANET at high speed.
Delay-bounded: channel acquisition and data transmission must be delay-bounded.
Scalability: the VANET should function as the number of vehicles increases.
Bandwidth efficiency: the radio resource should be utilized in an efficient and fair manner.
Fail-safe: no failure of any vehicle in the VANET should cause communication to fail among the remaining vehicles.
Fairness: every vehicle should get a fair chance to access the radio channels.
The present invention provides a novel channel allocation and access scheme for VANET that meets the above challenges.
There are three classes of existing MAC protocols of VANET that resolve contention among vehicles for channel access: contention-based, dynamic TDMA, and SDMA (Space Division Multiple Access).
Contention-based protocols use the Carrier Sense Multiple Access (CSMA) mechanism, in which vehicles transmit data only after sensing that the medium (radio channel) is idle. It is possible that more than one vehicle sense that the medium is idle and try to transmit at the same time. When that happens each transmitting vehicle will sense the data they sent is corrupted (due to a collision with data sent out by other vehicle(s) at the same time), and each vehicle will back off for a random or pre-defined period before making the next attempt. The vehicle will release the radio channel after the data transmission (usually limited to a maximum size data frame) is completed. It will need to compete with other vehicles again if there is more data to transmit, either immediately or at a later time.
There are two well-know content-based protocols for VANET:
IEEE 802.11p: The US has allocated the spectrum 5.855-5.925 GHz for Dedicated Short Range Communication (DSRC) to support ITS (Intelligent Transportation System) applications. The dominant DSRC standard for vehicular networks is IEEE 802.11p. Its medium access mechanism is based on the IEEE 802.11 Distributed Coordination Function (DCF), which basically is a Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) mechanism.
In dynamic TDMA (Time Division Multiple Access), radio spectrum is slotted into a sequence of time frames (windows), . . . , Fi−1, Fi, Fi+1, . . . , where each frame Fi contains a fixed number of time slots Si,1, Si,2, . . . Si,n. The same time slot in subsequent frames, e.g., Si,k, Si+1,k, Si+2,k, . . . form a channel that can be assigned to a vehicle, say V, which then can transmit data in the time slots of the assigned channel. The channel cannot be used by other vehicles until V releases it. Dynamically assigning the channels (time slots) to the vehicles (that join and leave the network) is the main task of any Dynamic TDMA scheme.
The RR-ALOHA (Reliable Reservation-ALOHA) is a distributed dynamic TDMA scheme that ensures that channels allocated to vehicles are unique among one-hop neighbors. A node A is a neighbor of another node B if and only if A is within transmission range of B and vice versa. That is, there is two-way communication capability between the nodes. RR-ALOHA is a modification of the original R-ALOHA (Reservation-ALOHA) scheme. R-ALOHA requires a central repeater through which all the vehicles in the network can obtain the slot allocation information. In VANET, such a central repeater is typically not available or feasible to implement. This deficiency is addressed by the distributed protocol of RR-ALOHA which relies solely on the peer vehicles, instead of on a central repeater, to ensure non-overlapping of the channels.
In this regard, some view Dynamic TDMA as a sub-class of contention-based schemes as the peer vehicles must work out to resolve the allocation of (or, competing for) time slots.
SDMA (Space Division Multiple Access) allocates time slots to vehicles based on their current locations. This approach requires each vehicle to be equipped with a positioning module (e.g. GPS positioning devices) so the vehicle can determine its current location. Without loss of generality, take for example a one-lane road. SDMA would divide the road into units, say 5-meter per unit, and assign a unique channel to each unit. The unit size is small enough to contain at most one vehicle and thus the vehicle can use the channel assigned to the unit without competition and interference from other vehicles. Channel re-use can also be achieved, e.g., by assigning the channels to the road units in a round-robin manner and requiring that the radio transmission range of each vehicle is less than the length of N consecutive units, where N is the total number of channels. This way, a vehicle can safely transmit on the channel assigned to it without worrying about interference caused by another vehicle that is transmitting at the same time on the same channel that is located N-unit way.
Contention-based schemes such as DSRC (e.g. IEEE 802.11p) and Dynamic TDMA (e.g. RR-ALOH) suffer from long delay when the density of vehicles increases. This is because more vehicles in the same region will result in higher likelihood of simultaneous data transmission and thus a significant increase in transmission collisions. When collisions occur, the vehicles will need to back off for a time period and retry, which again may result in another round of transmission collisions.
The non-contention based SDMA scheme, on the other hand, performs well when the vehicle density is extremely high, namely when each 5-meter unit is occupied with a single vehicle. However, the regular road traffic hardly sees one vehicle per 5-meter unit, except when traffic jam develops. At a relative sparse vehicle density, a large portion of the roadway will be unoccupied and the channels allocated to the units in this portion will be unused. This results in wasted radio bandwidth. One possible solution to this problem is to increase the size of the units, e.g. from 5-meter to 50-meters, to increase the likelihood that each unit is occupied by a vehicle. Doing such, however, will adversely create the possibility that more than one vehicle may be contained within a unit—a situation for which the existing SDMA does not provide a built-in mechanism to handle. Other prior solutions dynamically combine unused adjacent units into a “super-unit” and assign the aggregate channels to a vehicle traveling in the super-unit.
Contention-based schemes such as IEEE 802.11p and RR-ALOHA do not scale well at high frequencies of transmission requests. These schemes require a contention period for a vehicle to obtain a channel. When the vehicle density increases, more collisions occur to access the channels, which results in longer delay of message transfer and lower data transfer throughput. The R-SDMA scheme of the present invention mitigates this problem by limiting the number of vehicles that can contend for the channels. In accordance with the present invention, at most k vehicles in a region can contend from a channel pool of k channels assigned to the region. This reduces the probability of collision and reduces message transfer delay.
The SDMA scheme has a severe limitation in practice. The vehicle will spend much of its time performing “handoff” as it moves from unit to unit at high speed. In addition, when the vehicle density is sparse, most of the units will be unoccupied and thus the bandwidth of the channels assigned to those units will be wasted. The R-SDMA scheme of the present invention mitigates the above problems by having a larger size region than a SDMA unit (so handoff is performed less frequently), and by allowing a vehicle to gain multiple channels in a region (so the bandwidth is better utilized when vehicle density is sparse).